package org.example.myleet.p1608;

import java.util.Arrays;

public class Solution {
    public int specialArray(int[] nums) {
        //排序使得大于等于某个数的数字个数可以通过该数字下标直接求得
        Arrays.sort(nums);
        //外层二分：题目所求x值一定在0~最大的数字之间，又数字是有序排列好的，因此可以二分查找
        int l = 0, r = nums[nums.length - 1] + 1;
        while (l < r) {
            int x = (l + r) >> 1;
            //内层二分：找到x值对应的nums最接近的数字
            int l1 = 0, r1 = nums.length - 1;
            while (l1 < r1) {
                int m = (l1 + r1) >> 1;
                if (x < nums[m]) {
                    r1 = m;
                } else if (nums[m] < x) {
                    l1 = m + 1;
                } else {
                    l1 = m;
                    break;
                }
            }
            //由于可能存在相同数字，因此找到最接近的数字，要取排列顺序上的的第一个
            while (l1 > 0 && nums[l1 - 1] == nums[l1]) {
                --l1;
            }
            //O(1)复杂度求出大于等于当前l1下标的数字个数
            int count = nums.length - l1;
            if (nums[l1] < x) {
                //如果nums[l1]小于x，要排除掉所有和nums[l1]相同的数字
                int l2 = l1;
                while (l2 < nums.length && nums[l2] == nums[l1]) {
                    --count;
                    ++l2;
                }
            }
            if (x < count) {
                //count太多，说明x太小，左边界需要向右收缩
                l = x + 1;
            } else if (count < x) {
                //count太少，说明x太大，右边界需要向左收缩
                r = x;
            } else {
                //大于等于x的值的个数刚刚好有x个，输出答案
                return x;
            }
        }
        return -1;
    }
}
